package 单调栈;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/14 8:28
 */
public class lc496下一个更大的元素 {


    /*
     先写个 暴力
     */
    public int[] solve(int nums1[],int nums2[]){
        int len = nums1.length, ans[] = new int[len];
        for(int i = 0;i < len;i++){
            boolean flag = false;
            for(int j = 0;j < nums2.length;j++){
                if(nums1[i] == nums2[j]){
                    for(int k = j + 1;k < nums2.length;k++){
                        if(nums2[k] > nums1[i]){
                            ans[i] = nums2[k];
                            flag = true;
                            break; // 这里 也得break 一下
                        }
                    }
                    break; //这里提前结束一下
                }
            }
            if(!flag){
                ans[i] = -1;
            }
        }
        return ans;
    }


    /*
     单调栈的做法

     这个题的难度, 还稍微 降低了一点 (数组的元素不重复)
     */


    public int [] so(int nums1[],int nums2[]){
        int ans[] = new int[nums1.length];

        Deque<Integer> stack = new ArrayDeque<>(); // 用双端队列来模拟栈

        Map<Integer,Integer> map = new HashMap<>(nums2.length);
        int next[][] = new int[nums2.length][2];
        for(int i = 0;i  < nums2.length;i++){
            while(!stack.isEmpty() &&  nums2[stack.peekLast()] /*stack.peekLast()*/ < nums2[i]){ // 这里有重复元素 和无重复元素 处理不太一样
                Integer last = stack.removeLast();
                next[last][1] = i; // 这里也存储下标得了
                next[last][0] = stack.isEmpty() ? - 1 : stack.peekLast();
            }
            stack.addLast(i);
        }


        // 处理特殊情况
        while(!stack.isEmpty()){
            Integer last = stack.removeLast();
            next[last][1] = -1;
            next[last][0] = stack.isEmpty() ? - 1 : stack.peekLast();
        }
        return null;
    }


    @Test
    public void test(){
        int nums1[] = {4,1,2};
        int nums2[] = {1,3,4,2};

//        int[] solution = solution(nums1, nums2);
        System.out.println(Arrays.binarySearch(nums2,2));

    }

    public int [] solution(int nums1[],int nums2[]){
        int ans[] = new int[nums1.length];

        Deque<Integer> stack = new ArrayDeque<>(); // 用双端队列来模拟栈

        Map<Integer,Integer> map = new HashMap<>(nums2.length);
        for(int i = 0;i  < nums2.length;i++){
            while(!stack.isEmpty() &&  nums2[stack.peekLast()] /*stack.peekLast()*/ < nums2[i]){ // 这里有重复元素 和无重复元素 处理不太一样
                Integer last = stack.removeLast();
                map.put(nums2[last],nums2[i]);
            }
            stack.addLast(i);
        }


        // 处理特殊情况
        while(!stack.isEmpty()){
            Integer last = stack.removeLast();
            map.put(nums2[last],-1);
        }
        for(int i = 0;i < nums1.length;i++){
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }


/*
 稍微优雅一点的暴力
 */
    public int[] solution1(int nums1[],int nums2[]){
        int ans[] = new int[nums1.length];
        for(int i = 0;i < nums1.length;i++){
            for(int j = 0;j < nums2.length;j++){
                if(nums1[i] == nums2[j]){
                    ans[i] = -1;
                    for(int k = j + 1;k < nums2.length;k++){
                        if(nums2[k] > nums1[i]){
                            ans[i] = nums2[k];
                            j = nums2.length; // 提前终止一下！
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }

}
